#include "status.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef char datatype;
/**
  this program is used to distinguish whether an exp is right or not with bracket
  */
typedef struct snode{
	datatype data;
	struct snode *next;
}stack;
status init_stack(stack **s){
	(*s)=NULL;
	return ok;
}
status push(stack **s,datatype e){
	stack* node=(stack*)malloc(sizeof(stack));
	if(!node) exit(overflow);
	node->data=e;
	node->next=*s;
	(*s)=node;
	return ok;
}
status is_empty(stack *s){
	if(s==NULL)
		return ok;
	else 
		return error;
}
status pop(stack **s,datatype *e){
	if(is_empty(*s)){
		return error;
	}
	*e=(*s)->data;
	*s=(*s)->next;
	return ok;
}
status get_top(stack *s,datatype *e){
	if(is_empty(s)){
		return error;
	}
	*e=s->data;
	return ok;
}
void traverse(stack *s){
	stack *p;
	p=s;
	while(p){
		printf("%c ",p->data);
		p=p->next;
	}
	printf("\n");
}
char bracket[6]={'(',')','{','}','[',']'};
int pos_bracket(char e){
	for(int i=0;i<6;i++){
		if(e==bracket[i]){
			return i;
		}
	}
	return infeasible;
}
status exp_is_correct(char exp[],int n){
	stack *s;
	init_stack(&s);
	for(int i=0;i<n;i++){
		if(pos_bracket(exp[i])==-1){
			continue;
		}
		if(is_empty(s)){
			push(&s,exp[i]);
			continue;
		}
		datatype e;
		get_top(s,&e);
		int pos1=pos_bracket(e);
		int pos2=pos_bracket(exp[i]);
		if(pos2 %2==0){
			push(&s,exp[i]);
			continue;
		}
		if(pos1+1==pos2 && pos2%2==1){
			pop(&s,&e);
		}
	}
	if(is_empty(s))return true;
	else return false;
}
int main(){
	stack *s;
	init_stack(&s);
	push(&s,'a');
	push(&s,'b');
	push(&s,'c');
	push(&s,'e');
	push(&s,'f');
	push(&s,'g');
	traverse(s);
	char a1[]="(())abc{[]()";
	printf("%d\n",exp_is_correct(a1,strlen(a1)));
	char a2[]="(())abc[]()";
	printf("%d\n",exp_is_correct(a2,strlen(a2)));
	char a3[]="((())abc{[]()";
	printf("%d\n",exp_is_correct(a3,strlen(a3)));
	char a4[]="(())()abc[]()";
	printf("%d\n",exp_is_correct(a4,strlen(a4)));
	return 0;
}
